package acwing.算法题;/**
 * @author： li
 * @date： 2022-03-20 00:26
 * @version 1.0
 */
import java.util.*;
/*
* 原数据：1，999，100000，15；
* 处理后：1，3，4，2；
原数据：{100，200}，{20，50000}，{1，400}；
处理后：{3，4}，{2，6}，{1，5}；*/
public class 离散化 {
    static int[] a;//离散前的数组
    static int[] b;//离散化数组
    static int cnt=0;//离散化数组的长度
    //二分查找数的排名
    static int lower_bound(int x){
        int l=1,r =cnt;
        while(l<r){
            int mid=(l+r)>>1;
            if(b[mid]>=x)
                r=mid;
            else
                l=mid+1;
        }
        return r;
    }
    public static void main(String[] args) {
        //用set去重后 写个lower_bound(判断数的排名rank)
        Scanner sc = new Scanner(System.in);
        SortedSet<Integer> treeSet = new TreeSet<>();
//        HashSet<Integer> hashSet = new HashSet<>();
        int n=sc.nextInt();//n个数据
        a = new int[n+1];b = new int[n+1];//new数组
        for(int i=1;i<=n;i++){
            a[i] =sc.nextInt();//给离散数组和原数组赋值
            treeSet.add(a[i]);//hashSet的长度就是离散后离散数组的长度
        }

        System.out.println("原数组："+Arrays.toString(a));
        //也可以把上面的hashSet换成treeSet treeSet会直接排序 直接对treeSet进行二分就可以得到排名
        //对离散数组排序 得到排名
       int cut=1;
        for(Integer i :treeSet )
           b[cut++] = i;
        System.out.println("排序后离散数组："+Arrays.toString(b));
        //给原数组对应的值加上排名 就完成了离散化
        cnt=treeSet.size();//记得把去重后的长度减1赋值给cnt
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(a[i]);
        }
        System.out.println("离散后的数组："+Arrays.toString(a));
    }
}
